package algorithm.sort;

public class MaxHeap extends Common implements Sort {
    public void buildMaxHeap(int[] nums, int root, int outOfBorder) {
        int left = (root << 1) + 1;
        int right = (root << 1) + 2;
        int maxIndex = root;
        if (left < outOfBorder && nums[left] > nums[maxIndex]) {
            maxIndex = left;
        }
        if (right < outOfBorder && nums[right] > nums[maxIndex]) {
            maxIndex = right;
        }
        if (root != maxIndex) {
            swap(nums, maxIndex, root);
            buildMaxHeap(nums, maxIndex, outOfBorder);
        }
    }

    @Override
    public void execute(int[] nums) {
        execute(nums, type);
    }

    @Override
    public void execute(int[] nums, ImplementType methodType) {
        this.type = methodType;
        switch (methodType) {
        case DEFAULT:
        case DFS:
            for (int i = nums.length >> 1; i > 0; i--) {
                buildMaxHeap(nums, i, nums.length);
            }
            buildMaxHeap(nums, 0, nums.length);
            for (int i = nums.length - 1; i > 0; i--) {
                swap(nums, 0, i);
                buildMaxHeap(nums, 0, i);
            }
            break;
        case BFS:
            System.out.println("sorry I have't implement ");
        default:
            break;
        }
    }

}
